package org.basis.algorithm.sort;

import org.basis.algorithm.common.SortUtil;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author wenpan 2024/03/04 23:41
 */
public class InsertionSort {

    public static void main(String[] args) {
        final int count = 10000;
        // 使用对数器来对数
        for (int i = 0; i < count; i++) {
            int[] nums = SortUtil.generateRandomArray(100, 10000);
            int[] copyArray = SortUtil.copyArray(nums);

            process(nums);
            Arrays.sort(copyArray);

            if (!SortUtil.isEqual(nums, copyArray)) {
                System.out.println("插入排序出错...");
                break;
            }
        }
    }

    public static void process(int[] nums) {
        if (nums == null) {
            return;
        }
        // 要插入i轮
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                // 如果后面一个数比前一个还小，那么就把它换到前面去
                if (nums[j] < nums[j - 1]) {
                    SortUtil.swap(j, j - 1, nums);
                }
            }
        }
    }
}
